Use of hierarchical display lists in three dimensional computer graphics programs is well known. A display list contains a sequence of graphics commands which identify data structures and operations through which graphics data are retained and manipulated. Thus, a display list provides a means of organizing and executing graphics commands.
Typically, a display list contains "segments." Segments contain an ordered list of primitives, attributes of primitives or control functions, as well as light source and view descriptions. As is well known in the art, a primitive is a graphics element that defines a two dimensional or three dimensional entity, such as a surface of an object to be rendered in a three dimensional scene, and an attribute is a graphics element that defines a characteristic of the entity to be rendered, e.g., color, reflectivity, etc.
The segments of a display list can be organized in a multilevel structure wherein segments "call" other segments. This multilevel structuring scheme allows a hierarchy or network of segments to be constructed that closely parallels the application models they represent, hence, the term "hierarchical display list."
During execution of the graphics program, the display list is "traversed" and the various graphics commands of the display list are entered into a so called "three dimensional graphics pipeline" and the model is displayed, e.g., on a CRT. One example of such a program is the Starbase Display List graphics program sold by Hewlett-Packard Company, Palo Alto, Calif. Display list programs such as Starbase, however, render scenes according to a local illumination technique and do not generate global shading as part of the rendering process. Hence the displayed images are frequently not realistic. A global rendering technique, such as ray tracing or radiosity, provides more realistic shading in the rendering process, but the sequential format of the graphics information in the display list does not readily lend itself to global rendering. Global illumination requires that all data defining a surface in the scene be available in order to determine the effect of irradiated light of one surface upon all other surfaces. In a display list, the effect of light irradiated from a surface defined later in the display list upon a surface defined earlier in the display list cannot easily be determined since the earlier information has already been entered into the three dimensional graphics pipeline.
The two most common techniques employed for global rendering are ray tracing and radiosity. Both techniques are well known in the art. The following publications, which are incorporated herein by reference, are illustrative: Goral, Cindy M. et al., "Modeling the Interaction of Light Between Diffuse Surfaces", Computer Graphics, vol. 18, no. 3, pp. 213-222 (July, 1984); Cohen, Michael F. et al., "The Hemi-Cube: A Radiosity Solution For Complex Environments", SIGGRAPH Proceedings, vol. 19, no. 3, pp. 31-40 (1985); Greenberg, Donald P. et al. "Radiosity: A Method For Computing Global Illumination", The Visual Computer, vol. 2, pp. 291-297 (1986); Cohen, Michael F. et al., "An Efficient Radiosity Approach For Realistic Image Synthesis", IEEE CG&A, pp. 26-35 (March, 1986); Cohen, Michael F. et al., "A Progressive Refinement Approach to Fast Radiosity Image Generation", Computer Graphics, vol. 22, no. 4, pp. 75-84 (August, 1988). See also the following publications, incorporated herein by reference, which describe various ray tracing techniques: Wittig, Turner, "An Improved Illumination Model for Shaded Display", Communications of the ACM, 32,6 June 1980, pp. 343-349; Cook, Robert L. et al., "Distributed Ray Tracing", Computer Graphics, vol. 18, no. 3, pp. 137-145 (July, 1984). For implementation, both techniques require additional information that may not be immediately available in the display list. Thus, in the case of ray tracing (and by extension radiosity approaches that use ray tracing), a so called "bounding volume" around each three dimensional surface in the scene is often defined in order to increase the efficiency of determining ray-object intersections. The process of defining a bounding volume around such a surface is well known in the art, but nonetheless, this information may not be immediately available in a display list since it is not required for rendering a scene by local illumination. Additionally, in the case of radiosity, the various surfaces must be subdivided into a plurality of smaller surface elements (usually polygons being defined by a plurality of vertices) in order to carry out the radiosity algorithm. Again, however, this information is not immediately available in the display list. In the prior art, global rendering has been performed using special purpose modelers, not display lists.
It is therefore desirable to provide a method that renders display lists suitable for use with a global rendering technique. Since ray tracing and radiosity have their own strengths and weaknesses, it is further desirable that such method be adaptable so that it can be employed with either one of the these rendering techniques. The present invention achieves these objectives.